#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL 0
#define total_instruction 320
#define total_vp 32
#define clear_period 50

typedef struct {
    int pn;
    int pfn;
    int counter;
    int time;
} pl_type;

pl_type pl[total_vp];

typedef struct pfc_struct {
    int pn;
    int pfn;
    struct pfc_struct *next;
} pfc_type;

pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;
int diseffect, a[total_instruction];
int page[total_instruction], offset[total_instruction];
int initialize(int);
int FIFO(int);
int LRU(int);
int LFU(int);
int NUR(int);
int OPT(int);

int main() {
    int s, i, j;
    srand(10 * getpid());
    s = (float)319 * rand( ) / 32767 / 32767 / 2 + 1;
    for(i = 0; i < total_instruction; i += 4) {
        if( s < 0 || s > 319 ) {
            printf("When i==%d,Error,s==%d\n", i, s);
            exit(0);
        }
        a[i] = s;
        a[i + 1] = a[i] + 1;
        a[i + 2] = (float)a[i] * rand( ) / 32767 / 32767 / 2;
        a[i + 3] = a[i + 2] + 1;
        s = (float)(318 - a[i + 2]) * rand( ) / 32767 / 32767 / 2 + a[ i + 2] + 2;
        if((a[i + 2] > 318) || (s > 319))
            printf("a[%d+2],a number which is :%d and s==%d\n", i, a[i + 2], s);
    }
    for (i = 0; i < total_instruction; i++) {
        page[i] = a[i] / 10;
        offset[i] = a[i] % 10;
    }
    for (i = 4; i <= 32; i++){
        printf("--- %2d page frames --\n", i);
        FIFO(i);
        LRU(i);
        LFU(i);
        NUR(i);
        OPT(i);
    }
    return 0;
}

int initialize(int total_pf) {
    int i;
    diseffect = 0;
    for(i = 0; i < total_vp; i++) {
        pl[i].pfn = INVALID;
        pl[i].counter = 0;
        pl[i].time = -1;
    }
    for(i = 0; i < total_pf - 1; i++) {
        pfc[i].next = &pfc[i + 1];
        pfc[i].pfn = i;
    }
    pfc[total_pf - 1].next = NULL;
    pfc[total_pf - 1].pfn = total_pf - 1;
    freepf_head = &pfc[0];
    return 0;
}

int FIFO(int total_pf) {
    int i, j;
    pfc_type *p;
    initialize(total_pf);
    busypf_head = busypf_tail = NULL;
    for(i = 0; i < total_instruction; i++) {
        if(pl[page[i]].pfn == INVALID) {
            diseffect += 1;
            if(freepf_head == NULL) {
                p = busypf_head->next;
                pl[busypf_head->pn].pfn = INVALID;
                freepf_head = busypf_head;
                freepf_head->next = NULL;
            }
            p = freepf_head->next;
            freepf_head->pn = page[i];
            pl[page[i]].pfn = freepf_head->pfn;
            freepf_head->next = NULL;
            if(busypf_tail == NULL) {
                busypf_tail = busypf_head = freepf_head;
            } else {
                busypf_tail->next = freepf_head;
                busypf_tail = freepf_head;
            }
            freepf_head = p;
        }
    }
    printf("FIFO:%6.4f\n", 1 - (float)diseffect / 320);
    return 0;
}

int LRU (int total_pf) {
    int min, minj, i, j, present_time;
    initialize(total_pf);
    present_time = 0;
    for(i = 0; i < total_instruction; i++) {
        if(pl[page[i]].pfn == INVALID) {
            diseffect++;
            if(freepf_head == NULL) {
                min = 32767;
                for(j = 0; j < total_vp; j++) {
                    if(min > pl[j].time && pl[j].pfn != INVALID) {
                        min = pl[j].time;
                        minj = j;
                    }
                }
                freepf_head = &pfc[pl[minj].pfn];
                pl[minj].pfn = INVALID;
                pl[minj].time = 0;
                freepf_head->next = NULL;
            }
            pl[page[i]].pfn = freepf_head->pfn;
            pl[page[i]].time = present_time;
            freepf_head = freepf_head->next;
        } else {
            pl[page[i]].time = present_time;
            present_time++;
        }
    }
    printf("LRU:%6.4f\n", 1 - (float)diseffect / 320);
    return 0;
}

int NUR(int total_pf) {
    int i, j, dp, cont_flag, old_dp;
    pfc_type *t;
    initialize(total_pf);
    dp = 0;
    for(i = 0; i < total_instruction; i++) {
        if (pl[page[i]].pfn == INVALID) {
            diseffect++;
            if(freepf_head == NULL) {
                cont_flag = TRUE;
                old_dp = dp;
                while(cont_flag) {
                    if(pl[dp].counter == 0 && pl[dp].pfn != INVALID) {
                        cont_flag = FALSE;
                    } else {
                        dp++;
                        if(dp == total_vp)
                            dp = 0;
                        if(dp == old_dp)
                            for(j = 0; j < total_vp; j++)
                                pl[j].counter = 0;
                    }
                }
                freepf_head = &pfc[pl[dp].pfn];
                pl[dp].pfn = INVALID;
                freepf_head->next = NULL;
            }
            pl[page[i]].pfn = freepf_head->pfn;
            freepf_head->pn = page[i];
            freepf_head = freepf_head->next;
        } else
            pl[page[i]].counter = 1;
        if(i % clear_period == 0)
            for(j = 0; j < total_vp; j++)
                pl[j].counter = 0;
    }
    printf("NUR:%6.4f\n", 1 - (float)diseffect / 320);
    return 0;
}

int OPT(int total_pf) {
    int i, j, max, maxpage, d, dist[total_vp];
    pfc_type *t;
    initialize(total_pf);
    for(i = 0; i < total_instruction; i++) {
        if(pl[page[i]].pfn == INVALID) {
            diseffect++;
            if(freepf_head == NULL) {
                for(j = 0; j < total_vp; j++) {
                    if(pl[j].pfn != INVALID)
                        dist[j] = 32767;
                    else
                        dist[j] = 0;
                }
                for(j = 0; j < total_vp; j++) {
                    if((pl[j].pfn != INVALID) && (dist[j] == 32767)) {
                        dist[j] = j;
                    }
                }
                max = 0;
                for(j = 0; j < total_vp; j++)
                    if(max < dist[j]) {
                        max = dist[j];
                        maxpage = j;
                    }
                freepf_head = &pfc[pl[maxpage].pfn];
                freepf_head->next = NULL;
                pl[maxpage].pfn = INVALID;
            }
            pl[page[i]].pfn = freepf_head->pfn;
            freepf_head = freepf_head->next;
        }
    }
    printf("OPT:%6.4f\n", 1 - (float)diseffect / 320);
    return 0;
}

int LFU(int total_pf) {
    int i, j, min, minpage;
    pfc_type *t;
    initialize(total_pf);
    for(i = 0; i < total_instruction; i++) {
        if(pl[page[i]].pfn == INVALID) {
            diseffect++;
            if(freepf_head == NULL) {
                min = 32767;
                for(j = 0; j < total_vp; j++) {
                    if(min > pl[j].counter && pl[j].pfn != INVALID) {
                        min = pl[j].counter;
                        minpage = j;
                    }
                }
                freepf_head = &pfc[pl[minpage].pfn];
                pl[minpage].pfn = INVALID;
                pl[minpage].counter = 0;
                freepf_head->next = NULL;
            }
            pl[page[i]].pfn = freepf_head->pfn;
            pl[page[i]].counter++;
            freepf_head = freepf_head->next;
        } else {
            pl[page[i]].counter;
            pl[page[i]].counter = pl[page[i]].counter + 1;
        }
    }
    printf("LFU:%6.4f\n", 1 - (float)diseffect / 320);
    return 0;
}
